Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 843 - Crypt kicker / 843.2.cpp
blobb2593ff066a295ab756ab60e2d7d94a2ea489b81
1 #include <sstream>
2 #include <iostream>
3 #include <map>
4 #include <string>
5 #include <vector>
6 #include <set>
8 using namespace std;
10 map<int, set<string> > dict;
11 map<char, char> solucion;
14 bool contradice(const string &origen, const string &destino, map<char, char> crypt){
15 //cout << "Contradice llamado con " << origen << " y " << destino << endl;
17 map<char, char> temp;
18 for (int i=0; i<origen.size(); ++i){
19 if (temp.count(origen[i]) == 1){
20 if (temp[origen[i]] != destino[i]){
21 return true;
23 }else{
24 for (map<char, char>::iterator j = temp.begin(); j != temp.end(); ++j){
25 if ((*j).second == destino[i]) return true;
27 temp[origen[i]] = destino[i];
31 if (origen.length() != destino.length()) return true;
33 for (int i=0; i<origen.size(); ++i){
34 if (crypt.count(origen[i]) == 1){
35 if (crypt[origen[i]] != destino[i]){
36 return true;
38 }else{
39 for (map<char, char>::iterator j = crypt.begin(); j != crypt.end(); ++j){
40 if ((*j).second == destino[i]) return true;
44 return false;
49 void asignar(const string &origen, const string &destino, map<char, char> &crypt){
50 if (origen.size() != destino.size()) return;
52 for (int i=0; i<origen.size(); ++i){
53 crypt[origen[i]] = destino[i];
57 bool bt(int i, const vector<string> &words, map<char, char> crypt){
58 if (i >= words.size()){
59 solucion = crypt;
60 return true;
63 int len = words[i].length();
64 set<string> possible = dict[len];
66 for (set<string>::iterator j = possible.begin(); j != possible.end(); ++j){
68 /* if (!contradice(words[i], (*j), crypt)){
69 map<char, char> copia = crypt;
70 asignar(words[i], (*j), copia);
72 if (bt(i+1, words, copia)){
73 return true;
79 if (!contradice(words[i], (*j), crypt)){
80 map<char, char> copia = crypt;
81 asignar(words[i], (*j), copia);
83 if (bt(i+1, words, copia)){
84 return true;
90 return false;
93 int main(){
94 int n;
95 cin >> n;
96 while (n--){
97 string s;
98 cin >> s;
99 dict[s.length()].insert(s);
100 //cout << "agregue " << s << " al dict en la posicion " << s.length() << endl;
102 getchar();
103 string line;
104 while (getline(cin, line)){
105 //cout << "Lei esta linea: " << line << endl;
107 if (line == ""){
108 cout << "\n";
109 continue;
112 vector<string> words;
113 stringstream ss;
114 ss << line;
115 string word;
116 while (ss >> word){
117 words.push_back(word);
119 //cout << "Empuje la palabra " << word << " a la lista " << endl;
122 if (bt(0, words, map<char, char>() )){
123 for (int i=0; i<line.size(); ++i){
124 if (line[i] == ' ') cout << " ";
125 else cout << solucion[line[i]];
127 cout << endl;
128 //cout << "Hay solucion\n";
129 }else{
130 for (int i=0; i<line.size(); ++i){
131 if (line[i] == ' ') cout << " ";
132 else cout << "*";
134 cout << endl;
135 //cout << "No hay solucion\n";